package com.algrithom.graph.toposort;

import java.util.Stack;

/**
 * 拓扑排序 有向无环图的顶点的排序
 *
 * @author think
 * @version 1.0.0
 * @since 2020/2/20
 */
public class TopologicalSorting {
    
    public int count1 = 0;
    
    public Stack<Character> result = new Stack<>();
    
    public static void main(String[] args){
        TopologicalSorting test = new TopologicalSorting();
        int[][] adjMatrix = {{0,0,1,0,0},{0,0,1,0,0},{0,0,0,1,1},{0,0,0,0,1},{0,0,0,0,0}};

        int[] value = new int[5];
        test.dfs(adjMatrix,value);
        System.out.println();
        System.out.println("使用ＤＦＳ方法得到拓扑排序序列的逆序：");
        System.out.println(test.result);
        System.out.println("使用ＤＦＳ方法得到拓扑排序序列：");
        while (!test.result.empty()) {
            System.out.print(test.result.pop() + "\t");
        }
    }
    
    /**
     * @param adjMatrix 是待遍历图的邻接矩阵
     * @param value 是待遍历图顶点用于是否被遍历的判断依据，0代表未遍历，非0代表已被遍历
     */
    public void dfs(int[][] adjMatrix,int[] value){
        for (int i = 0; i < value.length; i++) {
            if (value[i] == 0) {
                dfsVisit(adjMatrix,value,i);
            }
        }
    }
    
    /**
     * @param adjMatrix 是待遍历图的邻接矩阵
     * @param value 是待遍历图顶点用于是否被遍历的判断依据，0代表未遍历，非0代表已被遍历
     * @param number 是当前正在遍历的顶点在邻接矩阵中的数组下标编号
     */
    public void dfsVisit(int[][] adjMatrix,int[] value,int number){
        // 把++count1赋值给当前正在遍历顶点判断值数组元素，变为非0，代表已被遍历
        value[number] = 1;
        for (int i = 0; i < value.length; i++) {
            // 当，当前顶点的相邻有相邻顶点可行走且其为被遍历
            if (adjMatrix[number][i] == 1 && value[i] == 0) {
                dfsVisit(adjMatrix,value,i);
            }
        }
        char temp = (char)('a' + number);
        result.push(temp);
    }
}
